/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        92.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/12 22:13
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
#include "../header.h"

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (m == 1)
            return reverseN(head, n);
        head->next = reverseBetween(head->next, m - 1, n - 1);
        return head;
    }

private:
    // 反转前n个, 返回头节点
    ListNode *successor = nullptr;

    ListNode *reverseN(ListNode *head, int n) {
        if (n == 1) {
            successor = head->next;
            return head;
        }
        ListNode *last = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = successor;
        return last;
    }
};